package com.algorithm.getIntersectionNode;

import com.algorithm.Common.LinkedNode;
import com.algorithm.Common.LinkedUtils;

public class AlMain {
    public static void main(String[] args) {
        LinkedNode node1 = LinkedUtils.create(new int[]{5, 6, 7, 8, 9});
        LinkedNode node2 = LinkedUtils.create(new int[]{1, 2, 3, 4});
        LinkedNode node3 = LinkedUtils.create(new int[]{10, 11, 12});
        LinkedNode p1 = node1, p2 = node2;
        while (p1.getNext() != null) {
            p1 = p1.getNext();
        }
        p1.setNext(node3);
        while (p2.getNext() != null) {
            p2 = p2.getNext();
        }
        p2.setNext(node3);
        System.out.println(getIntersectionNode(node1, node2).getData());;
    }

    public static LinkedNode getIntersectionNode(LinkedNode headA, LinkedNode headB) {
        int lenA = 0, lenB = 0;
        LinkedNode p = headA, q = headB;
        while (p != null) {
            lenA++;
            p = p.getNext();
        }
        while (q != null) {
            lenB++;
            q = q.getNext();
        }
        p = headA;
        q = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p = p.getNext();
            }
        }
        if (lenB > lenA) {
            for (int i = 0; i < lenB - lenA; i++) {
                q = q.getNext();
            }
        }
        while (p != null && q != null) {
            if (p == q) {
                return p;
            }
            p = p.getNext();
            q = q.getNext();
        }
        return null;
        }
    }

